#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <set>
using namespace std;

int SubLongestParentheses(string &s, int iBegin, int &vBegin){
    if(iBegin > s.length() - 2)
        return 0;

    int left = 0;
    int length = 0;
    for(int i=iBegin; i<s.length(); ++i){
        if(s[i] == '('){
            ++left;
        }
        else{
            // ')'
            if(left > 0){
                --left;
                length += 2;
                if(left == 0){
                    // begin new point
                    vBegin = i - length + 1;
                    int subBegin;
                    int subLength = SubLongestParentheses(s, i+1, subBegin);
                    if(subLength >0 && subBegin == i+1){
                        return subLength + length;
                    }
                    else{
                        if(subLength > length){
                            vBegin = subBegin;
                            return subLength;
                        }
                        else{
                            return length;
                        }
                    }
                }
            }
            else{
                int subBegin;
                int subLength = SubLongestParentheses(s, i+1, subBegin);
                if(subLength > length){
                    vBegin = subBegin;
                    return subLength;
                }
                else{
                    vBegin = i - length + 1;
                    return length;
                }
            }
        }
    }
    vBegin = s.length() - length;
    return length;
}

int longestValidParentheses(string s) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if(s.length() < 2)
        return 0;
    map<int, int> segs;
    map<int, int> rsegs;
    stack<int> pos;
    for(int i=0; i<s.length(); ++i){
        if(s[i] == '('){
            pos.push(i);
        }
        else{
            // ')'
            if(pos.size() > 0){
                int begin = pos.top();
                pos.pop();
                segs[begin] = i;
                rsegs[i] = begin;
            }
        }
    }
    // walk segs
    int res = 0;
    set<int> visited;
    for(map<int, int>::iterator it = segs.begin();
        it != segs.end();
        ++it){

        if(visited.find(it->first) != visited.end()){
            // walked
            continue;
        }
        int left = it->first;
        int right = it->second;
        visited.insert(it->first);
        // walk left
        map<int, int>::iterator leftit = rsegs.find(left-1);
        while(leftit != rsegs.end()){
            left = leftit->second;
            visited.insert(left);
            leftit = rsegs.find(left-1);
        }
        // walk right
        map<int, int>::iterator rightit = segs.find(right+1);
        while(rightit != segs.end()){
            right = rightit->second;
            visited.insert(rightit->first);
            rightit = segs.find(right+1);
        }
        int length = right - left + 1;
        if(length > res){
            res = length;
        }

    }
    return res;   
}




int main(){
    cout<<longestValidParentheses("()(()")<<endl;
    return 0;
}